Genetic Algorithms and Applications
Fall 2023
MW 13:00-14:15
Course Outline: This course provides heuristic approach in optimization. It includes Genetic algorithms (GAs) and Tabu search. Genetic representation, selection, operators, niche, and parallelism are discussed in GAs. Tabu moves, tenure, aspiration criteria, short term and long term memories are examined in Tabu search. Theoretical improvements of the methods are examined for both the solution quality and computational complexity. Applications to various optimization problems are discussed.
Professor
Dr. Chae
Young Lee
Phone: (042) 350-2916
Office: Room 4208 at E2-1
Office hours: M W 9:30-11:00
Teaching Assistant
Phone: (042) 350-
Office: Room at E2-1
Office hours: T TH 14:30-16:00
Grading
Mid-term
(25%) Date: 10/11
Final (25%) Date: 12/6
Homework (10%)
Paper presentation (20%)
Term project (20%)
The Texts
Genetic Algorithms, by
Goldberg, Addison Wesley, 1989
Tabu Search, by Glover and Laguna,
Kluwer Academic Publishers, 1997
Schedule
Date |
Topics |
Read |
Problems |
8/28 |
Introduction to GAs |
Chap. 1 |
|
8/30 |
What is GA? A GA by hand |
|
|
9/4 |
Schemata, Schema theorem |
Chap. 2 |
|
9/6 |
Implicit parallelism, Building block hypothesis |
P1, P2 |
|
9/11 |
Deception, Decision making |
|
|
9/13 |
A simple GA in Pascal |
Chap. 3 |
1, 2 |
9/18 |
Selection schemes |
Chap. 4 |
2, 3, 4, 5 |
9/20 |
Selection schemes |
P3 |
|
9/25 |
Parallel GAs |
P4 |
|
9/27 |
Selection schemes |
P5 |
|
10/2 |
Order-Based GAs, Graph Coloring Problem |
|
|
10/4 |
Reordering, Inversion operator |
Chap. 5 |
|
10/11 |
Mid-term Exam |
||
10/23 |
Real code representation |
P6, P7, P8, P9 |
|
10/25 |
Niching, Crowding, Sharing |
Chap. 5 |
|
10/30 |
Nitching |
P10, P11 |
|
11/1 |
Dominance, Diploidy |
Chap. 5 |
1, 2, 3, 11 |
11/6, 98 |
Convergence and Diversity |
P12 |
|
11/13, |
Introduction to Tabu Search |
Chap. 1, P13 |
|
11/15 |
Short term memory |
Chap. 2, 3 |
|
11/20 |
Long term memory |
Chap. 4 |
|
11/22 |
Parametric Tabu Search |
P14 |
|
11/27 |
Presentation of term projects |
|
|
11/29 |
Presentation of term projects |
|
|
12/4 |
Presentation of term projects |
|
|
12/6 |
Final Exam |
|
|
|
|
|
Paper Reading List
[P1] Mitchel, M. and Forrest, S., Relative Building Block Fitness and Building-Block Hypothesis, Proceedings of Foundations of GAs, 109-126, 1992.
[P2] Mitchel, M., Royal Roads, 127-138, An Introduction to GAs, The MIT Press, 1996.
[P3] Goldberg D.E., A Comparative Analysis of Selection Schemes used in Genetic Algorithms, Proceedings of Foundations of GAs, 69-93 1991.
[P4] Gordon, S. and Whitley, D., Serial and Parallel Genetic Algorithms as Function Optimizer, Proceedings of 5th International Conference on GAs, 177-183, 1993.
[P5] De Jong, K and Sarma, J, On Decentralizing Selection Algorithms, Proceedings of 6th ICGA, 9-16, 1995.
[P6] Eshelman, L.J. and Schaffer, J.D., Real-Coded Genetic Algorithms and Interval-Schemata, Proceedings of Foundations of GAs, 187-202, 1993
[P7] Mathias, K.E. and Whitley, D., Changing Representation During Search: A Comparative Study of Delta Coding, Evolutionary Computation, 2(3), 249-278, 1994.
[P8] Falkenauer, E., A New Representation and Operators for Genetic Algorithms Applied to Grouping Problems, Evolutionary Computation, 2(2), 123-144, 1994.
[P9] Tucker, Allan et al., RGFGA: An Efficient Representation and Crossover for Grouping Genetic Algorithms, Evolutionary Computation 13(4), 477-499, 2005.
[P10] Mahfoud, S.W., A Comparison of Parallel and Sequential Niching Methods, Proceedings of 6th ICGA, 136-143, 1995.
[P11] Horn, J. and Goldberg, D.E.,Toward a Control Map for Nitching, Proceedings of Foundations of GAs, 287-310, 1999
[P12] Laumanns, M. et al., Combining Convergence and Diversity in Evolutionary Multiobjective Optimization, Evolutionary Computation 10(3), 263-282, 2002.
[P13] Glover, F., Tabu Search: A Tutorial, Interfaces, 20(4), 74-94, 1990.
[P14] Glover, F., Parametric Tabu Search for Mixed Integer Programs, Computers and Operations Research, 33, 32449-2494, 2006.